//给定一棵二叉搜索树，请找出其中的第k小的结点。 例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
//二叉搜索树的中序遍历即排序后的节点，本题实际考察二叉树的遍历。

//递归实现
function KthNode(pRoot,k){
    const arr = [];
    //进行一次中序遍历，遍历后的结果即是排序后的节点
    middleOrder(pRoot,arr);
    if(k>0 && k<=arr.length){
        return arr[k-1];
    }
    return null;
}

function middleOrder(node,arr){
    if(node){
        middleOrder(node.left,arr);
        arr.push(node);
        middleOrder(node.right,arr)
    }
}

//非递归实现
function KtnNode(pRoot,k){
    const arr =[];
    const stack = [];
    let current = pRoot;
    while(stack.length >0 || current ){
        while(current){
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        arr.push(current);
        current = current.right;
    }
    if(k>0 && k<=arr.length){
        return arr[k-1];
    }
    return null;
}